#include <iostream>
using namespace std;

//弧结点
struct ArcNode {
    int adjvex;
    ArcNode *nextarc;
};

//顶点结点
struct VexNode {
    char data;
    ArcNode *firstarc;
};

//邻接表
#define M 100
struct ALGraph {
    VexNode vexs[M];
    int vexnum, arcnum;
};

//初始化空的图G
void InitGraph(ALGraph &G)
{
    G.vexnum = G.arcnum = 0;
}

//在图G中增加数据为data的顶点，返回顶点编号
int AddVertex(ALGraph &G, char data)
{
    if(G.vexnum >= M) throw "Graph is full";
    G.vexs[G.vexnum++] = {data, nullptr};
    return G.vexnum - 1;
}

//在图G中增加弧v1-v2
void AddArc(ALGraph &G, int v1, int v2)
{
    if(v1 < 0 || v1 >= G.vexnum || v2 < 0 || v2 >= G.vexnum)
        throw "Vertex not found";
    G.vexs[v1].firstarc = new ArcNode{v2, G.vexs[v1].firstarc};
    G.arcnum++;
}

//销毁邻接表G
void DestroyGraph(ALGraph &G)
{
    for(int i = 0; i < G.vexnum; i++){
        auto p = G.vexs[i].firstarc;
        while(p) {
            auto q = p;
            p = p->nextarc;
            delete q;
        }
    }
}

void Print(const ALGraph &G)
{
    for(int i = 0; i < G.vexnum; i++) {
        cout << G.vexs[i].data << ": ";
        for(auto p = G.vexs[i].firstarc; p; p = p->nextarc)
            cout << G.vexs[p->adjvex].data << " ";
        cout << endl;
    }
}

int main()
{
    //创建图的邻接表
    ALGraph G;
    InitGraph(G);
    int a = AddVertex(G, 'A');
    int b = AddVertex(G, 'B');
    int c = AddVertex(G, 'C');
    int d = AddVertex(G, 'D');
    int e = AddVertex(G, 'E');
    AddArc(G, a, b);
    AddArc(G, a, c);
    AddArc(G, b, c);
    AddArc(G, b, d);
    AddArc(G, c, d);
    AddArc(G, d, a);
    AddArc(G, e, a);
    AddArc(G, e, d);

    //打印邻接表
    Print(G);

    //销毁图
    DestroyGraph(G);

    return 0;
}